Existing computer programs known as road-mapping programs provide digital maps, often complete with detailed road networks down to the city-street level. Typically, a user can input a location and the road-mapping program will display an on-screen map of the selected location. Several existing road-mapping products typically include the ability to calculate a best route between two locations. In other words, the user can input two locations, and the road-mapping program will compute the travel directions from the source location to the destination location. The directions are typically based on distance, travel time, etc. Computing the best route between locations may require significant computational time and resources.
Some road-mapping programs compute shortest paths using variants of a well known method attributed to Dijkstra. Note that in this sense “shortest” means “least cost” because each road segment is assigned a cost or weight not necessarily directly related to the road segment's length. By varying the way the cost is calculated for each road, shortest paths can be generated for the quickest, shortest, or preferred routes. Dijkstra's original method, however, is not always efficient in practice, due to the large number of locations and possible paths that are scanned. Instead, many known road-mapping programs use heuristic variations of Dijkstra's method.
More recent developments in road-mapping algorithms utilize a two-stage process comprising a preprocessing phase and a query phase. During the preprocessing phase, the graph or map is subject to an off-line processing such that later real-time queries between any two destinations on the graph can be made more efficiently. Known examples of preprocessing algorithms use geometric information, hierarchical decomposition, and A* search combined with landmark distances.
Most previous research focused on a metric directed to driving times. Real-world systems, however, often support other metrics such as shortest distance, walking, biking, avoiding U-turns, avoiding freeways, preferring freeways, or avoiding left turns, for example. Current road-mapping techniques are not adequate in such scenarios. The preprocessing phase is rerun for each new metric, and query times may not be competitive for metrics with weak hierarchies. The preprocessing phase can be costly, limiting the ability to incorporate new optimization functions, including traffic information and personal preferences.